package BinaryTree;

import java.util.ArrayList;
import java.util.List;
/*class TreeNode {
	  int val;
	  TreeNode left;
	  TreeNode right;
	  TreeNode() {}
	  TreeNode(int val) { this.val = val; }
	  TreeNode(int val, TreeNode left, TreeNode right) {
	      this.val = val;
	      this.left = left;
	      this.right = right;
	  }
}*/

public class Code2 {
	
    //时间复杂度: O(n)
	//按层处理的bfs,推荐
	public static int MAXN=2001;
	//用数组模拟队列
    public static TreeNode[] queue=new TreeNode[MAXN];
    //l,r表示当前的实际存储空间，区间为[l,r)
    public static int l,r;
    public List<List<Integer>> levelOrder(TreeNode root) {
    	
        List<List<Integer>> ans=new ArrayList<>();
        
        if(root!=null){
            l=r=0;    //由于是l,r和queue是静态成员，因此每次进入函数都将l,r置空，表示无元素
            queue[r++]=root;    //一开始先插入头节点
            
            while(l<r){
            	//有效区间为[l,r)，故当l==r时，表示队列为空
                int size=r-l;     //获取当前层队列的长度
                
                List<Integer> list=new ArrayList<>();
                for(int i=0;i<size;i++){      //将该层的元素依次出队列，其左右孩子入队列
                    
                	TreeNode cur=queue[l++];  //l++表示出队列
                    list.add(cur.val);
                    
                    if(cur.left!=null){
                        queue[r++]=cur.left;
                    }
                    if(cur.right!=null){
                        queue[r++]=cur.right;
                    }
                }
                ans.add(list);
            }
        }
        return ans;
    }
}
